<?php
/**
 * SimplifyPHP Framework
 *
 * This file is part of SimplifyPHP Framework.
 *
 * SimplifyPHP Framework is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * SimplifyPHP Framework is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * @author Rodrigo Rutkoski Rodrigues, <rutkoski@gmail.com>
 */

/**
 * Implements the Trie data structure. http://en.wikipedia.org/wiki/Trie
 *
 * @author Rodrigo Rutkoski Rodrigues, <rutkoski@gmail.com>
 * @package Simplify_Kernel_Data
 */
class Trie
{

  /**
   *
   * @var unknown_type
   */
  protected $data = array();

  /**
   *
   * @var unknown_type
   */
  protected $d = array();

  /**
   *
   */
  public function get($name)
  {
    if (isset($this->d[$name])) {
      return $this->d[$name];
    }
    else {
      list ($c, $k) = $this->getCollision($name);
      
      if (isset($this->d[$c])) return $this->d[$c]->get(substr($name, strlen($c)));
    }
    
    throw new NotFoundException('Key not found in tree');
  }

  /**
   *
   */
  public function set($name, $value)
  {
    list ($c, $k) = $this->getCollision($name);
    
    if (strlen($c)) {
      if ($c != $k) {
        $_k = substr($k, strlen($c));
        $_v = $this->d[$k];
        
        unset($this->d[$k]);
        
        $this->d[$c] = new Trie();
        $this->d[$c]->set($_k, $_v);
      }
      
      $this->d[$c]->set(substr($name, strlen($c)), $value);
    }
    else {
      $this->d[$name] = new Trie();
      $this->d[$name] = $value;
    }
  }

  /**
   *
   */
  protected function getCollision($name)
  {
    $i = 1;
    $c = null;
    $f = true;
    $d = array_keys($this->d);
    $k = null;
    
    while ($i <= strlen($name) && $f) {
      $l = substr($name, 0, $i);
      $j = 0;
      
      while ($j < count($d) && strpos($d[$j], $l) !== 0)
        $j ++;
      
      if ($j < count($d)) {
        $c = substr($d[$j], 0, $i);
        $k = $d[$j];
      }
      else {
        $f = false;
      }
      
      $i ++;
    }
    
    return array(
      $c, 
      $k
    );
  }
}

?>